In this chapter, we study a graph-theoretic game called the Bounded Budget Connection (BBC) game where strategic nodes acting under a cost budget form connections with a view to optimizing their proximity to the other nodes in the network. Specifically, the problem is specified by a set of nodes, each with a budget to spend on directed edges from itself to other nodes. Each potential edge has an associated cost, and each node has a length metric for the entire network.  A node will choose which edges to buy, without exceeding its budget, to create the shortest possible paths to the other nodes in the network. We consider two cases: first, where each node is trying to minimize the weighted average shortest path distance to the other nodes (given an affinity for each other node), and second, where each node is trying to minimize the maximum shortest path distance to any other node. This game has a number of real-world applications.

\begin{itemize}
\item \BfPara{Peer-to-peer file sharing} A peer-to-peer filesharing system uses an overlay of self-defined neighbors for communication. Since nodes may make constant use of flooding or broadcast messages, and since the system will need to maintain and distribute link state information, we want to restrict the number of allowed neighbors. Each node will independently choose its outgoing edges in an attempt to minimize its average latency to the nodes of interest.

\item \BfPara{Social networking} Most social networks currently do not limit the number of allowed connections, but natural bounds on people's time and cognitive resources make it infeasible for users to maintain many direct ties. This is referred to as the Dunbar limit in sociology literature. Furthermore, in a social network that requires a good deal of time and effort to maintain a meaningful connection, it may be worthwhile to investigate explicitly bounding the allowed number of relations. When the number of connections is limited, users would have to utilize friends of friends, and friends of friends of friends, etc. if they want to influence the entire network. 
\end{itemize}

The space of BBC games is vast, since it allows for a variety
of models to capture different situations. In addition to different notions of
connection cost and proximity e.g., fractional and integral, symmetric and asymmetric,
uniform and nonuniform, metric spaces, etc., one can also consider 
the dynamics of the resultant complex
systems. We believe the budget constraint is an important real-world restriction
and consider our study to be a preliminary step towards understanding 
and characterizing the rich and elegant structures that exist in this domain. 

In Section \ref{sec:bbc_definition}, we formally define general BBC games. Section \ref{sec:bbc_related} discusses related work, primarily on other network creation games. Section \ref{sec:bbc_results} lists our results which are proved in the remainder of the chapter. Section \ref{sec:bbc_nonuniform} discusses hardness results for the general game with the average distance utility function. Section \ref{sec:bbc_uniform} gives a number of results for the ``uniform'' version, in which all nodes have the same budget, all edges have the same cost and length, and each node equally desires to access each other node. Finally, Section \ref{sec:bbc_max} extends the results to the case with the max distance utility function.

\section{Definition} \label{sec:bbc_definition}

A BBC game is specified by a tuple $\langle V, \prefnoargs, \costnoargs, \budgetnoargs\rangle$, and a length function, $\lengthonearg{u}$ for each $u \in V$, where $V$ is a set of nodes, $\prefnoargs: V \times V \rightarrow
\mathbb{Z}$, $\costnoargs: V \times V \rightarrow \mathbb{Z}$, $\budgetnoargs: V \rightarrow \mathbb{Z}$, and $\lengthonearg{u}: V \times V \rightarrow
\mathbb{Z}$ (for each $u \in V$) are functions.  For any $u, v \in V$, $\affinity{u}{v}$ indicates $u$'s
affinity for communicating with $v$, $\cost{u}{v}$ denotes the cost
of directly linking $u$ to $v$, and $\length{x}{u}{v}$ denotes the length
of the link $(u,v)$ from the perspective of $x$, if $u$ has established this link.  For any node $u \in V$,
$\budget{u}$, specifies the budget $u$ has for establishing outgoing
directed links: the sum of the costs of the links $u$ establishes
should not exceed $\budget{u}$.

A strategy for node
$u$ is a subset $S_u$ of $\{(u,v): v \in V\}$ such that $\sum_{v:
(u,v) \in S_u} \cost{u}{v} \le \budget{u}$.  Let $S_u$ denote a
strategy chosen by node $u$ and let $S =
\{S_u: u \in V\}$ denote the collection of strategies.  The network
formed by $S$ is simply the directed graph $G(S) = (V,E)$ where $E =
\bigcup_u S_u$.  The utility of a node $u$ in $G(S)$ is given by
$- \sum_{v} \affinity{u}{v} d(u,v)$, where $d(u,v)$ is the shortest path
from $u$ to $v$ in $G(S)$ according to the lengths given by
$\lengthonearg{u}$.  For convenience, we assume that if no path exists in
$G(S)$ from $u$ to $v$, then $d(u,v)$ is given by some
large integer $M \gg n\max_{x,u,v} \length{x}{u}{v}$; we refer to $M$ as
the {\em disconnection penalty}.

Following the standard game-theoretic terminology, we say that a
strategy selection $S = \{S_u: u \in V\}$ is stable if it is a pure
Nash equilibrium for the BBC game; in particular, for each $u$, $S_u$
is an optimal strategy for $u$ assuming that the strategy for every $v
\neq u$ is fixed as in $S$.

One focus of our work is on {\em uniform games}, in which (a)
$\cost{u}{v}$ is identical for all $u, v$; (b) $\affinity{u}{v}$ is
identical for all $u, v$; (c) $\length{x}{u}{v}$ is identical for all $x, u,
v$; and (d) $\budget{u}$ is identical for all $u
\in V$.  In a uniform game, we may assume without loss of generality
that $\cost{u}{v} = \affinity{u}{v} = \length{x}{u}{v} = 1$ for all $u,v,x$,
and $\budget{u} = k$, for all $u \in V$, for some integer $k$.  We
refer to the preceding uniform game as an $(n,k)$-uniform game where
$n = |V|$.  We refer to BBC games that are not uniform as {\em
non-uniform}\/ games.

Another focus is on \emph{fractional games}, which will be defined and discussed in Chapter \ref{sec:fractionalGames}.

\section{Related Work}
\label{sec:bbc_related}
Notions of group and network formation have 
been investigated by a number of different 
communities starting with researchers in economics and game theory
and followed by work in combinatorial optimization and computer science.
The work of \cite{JacksonWolinsky96} modeled and analyzed the
stability of networks when nodes themselves choose to form or sever links;
their model is different from ours in that they studied different stylized models
that included production and allocation functions under the (relatively weak)
concept of pairwise stability, along with side payments. \cite{BalaGoyal00} studies
a model of directed network formation where nodes incur costs based on the 
number of incoming links.
In \cite{FabrikantLMPS03}, where they defined and studied a similar
network creation game, the authors do not have a fixed budget of directed links 
for the nodes; instead they consider undirected links, and the nodes
optimize a cost which is the sum of the number of edges, scaled by a
parameter $\alpha > 0$, and the sum of distances to the rest of the
nodes.  They present several results on the price of anarchy, which is
the ratio of the cost of the worst-case Nash equilibrium to the social
optimum cost~\cite{KoutsoupiasPapadimitriou99}.  Further results in this direction are 
obtained in~\cite{AlbersEEMR06} and ~\cite{DemaineHM07}. \cite{HaleviMansour07} extends this model to the case where each node is only interested in connecting to a subset of the other nodes. \cite{Even-DarKearns06} is similar to \cite{FabrikantLMPS03}
in that they impose a cost for the purchase of a link rather than a fixed budget. However,
they consider a stochastic model and associated small-world effects.  
In~\cite{MoscibrodaSW06}, a variant is studied in which the 
nodes are embedded in a metric space and
the distance component of the cost is replaced by the stretch with
respect to the metric. They obtain tight bounds on the price of
anarchy and show that the problem of deciding the existence of pure
Nash equilibria is \NP-hard. Network formation under the requirement 
for bilateral consent for building links is studied in~\cite{CorboParkes05}. \cite{Evan-DarKS07} focuses on a similar network creation game restricted to a bipartite graph, with nodes representing buyers and sellers.
Our model follows directly in the tradition of 
\cite{ChunFSK04,LaoutarisSBB07} where they present experimental 
studies of network formation games involving non-unit link lengths. 

Combinatorial optimization aspects are explored in \cite{KempeKT03, KempeKT05}, 
where the goal is to pick an initial set in a stochastic model with maximal 
expected influence. This model is extended further in \cite{BharathiKS07} to a 
competitive setting within the stochastic framework where different players 
compete (sequentially) to maximize their expected influence. 

\section{Our Results}
\label{sec:bbc_results}
The results in this section are published in \cite{OurPODC08}. Our goal is to study the structural and complexity-theoretic
properties of pure Nash equilibria in BBC games. We first present our results on the most general, nonuniform BBC games. 

\begin{itemize}
\item We show that determining the existence of a pure Nash equilibrium in nonuniform BBC games
is \NP-hard. To be precise, we show the \NP-hardness of determining the existence of a pure Nash equilibrium
when link lengths and affinity weights are nonuniform. We also show that a pure Nash equilibrium may not exist if either 
cost or affinity is nonuniform.
\end{itemize}

Next, we present results on uniform BBC games. We can assume, without loss of generality, that
all link weights, link lengths and affinity weights are equal to $1$ and all budgets are equal to $k$,
thus allowing us to talk of $(n,k)$-uniform BBC games.

\begin{itemize}
\item We show that a pure Nash equilibrium or stable graph exists for all $(n,k)$-uniform BBC games
and that all stable graphs are essentially fair (i.e., all nodes have similar costs). We provide
an explicit construction of a family of stable graphs that spans the spectrum from minimum 
to maximum total social cost. To be precise we show that the price of stability
is $\Theta(1)$, and the price of anarchy is $\Omega(\frac{\sqrt{n/k}}{\log_k n})$ and $O(\sqrt{\frac{n}{\log_k n}})$.
Observe that our bounds for the price of anarchy are nearly tight when $k$ is a constant.
\end{itemize}

We consider the dynamics of best response moves in uniform BBC games.
\begin{itemize}
\item We show that in any $(n,k)$-uniform BBC game, a (suitably defined and entirely natural) 
best response walk converges to a strongly connected configuration within $n^2$
steps.
\item We show that uniform BBC games are not (ordinal) potential games by presenting a loop
for best response walks. This serves to underscore the
importance of our explicit constructions of stable graphs, as it rules out the possibility of demonstrating
existence of Nash equilibria through suitably defined potential functions.
\end{itemize}

We show that there are analogous results for the case where the cost function is the 
maximum (instead of the sum) of the weighted distances. We call this a \emph{max-BBC} game.
\begin{itemize}
%\item Determining the existence of a pure Nash equilibrium in general max-BBC games is NP-hard.
\item There are examples of max-BBC games for which no pure Nash equilibrium exists.
\item A pure Nash equilibrium exists for all $(n, k)$-uniform max-BBC games. The price of stability is $\Theta(1)$, and the price of anarchy is $\Omega(\frac{n}{k \log_k n})$, $O(\frac{n}{log_k n})$.
\end{itemize}

\section{Nonuniform Games}\label{sec:bbc_nonuniform}
%
In this section we show there exist instances of non-uniform BBC games
that do not have a pure Nash equilibrium.  Furthermore, we prove that
it is \NP-hard to determine whether a given instance of a non-uniform
BBC game has a pure Nash equilibrium.  
\junk{This motivates us to consider a
natural variant of BBC games, which we call {\em fractional BBC
games}, in which each node can select {\em fractions}\/ of links,
whose total cost is within the node budget.  We show that pure Nash
equilibria always exist for fractional non-uniform BBC games.}

\subsection{Nonexistence of pure Nash equilibria and \NP-hardness}
\label{sec:nonuniform.nonexistence}

The following theorem is subsumed by Theorem \ref{thm:nonexistence2}, but the proof includes a very simple example of a BBC game with no pure Nash equilibrium. We will reuse this example in the proof of Theorem \ref{thm:nphard}.

\begin{theorem}\label{thm:nonexistence}
For any $k \ge 1$, $n \geq k^2 + k + 4$ there exists a nonuniform BBC game with no pure Nash equilibrium with $n$ nodes, a budget of $k$ per node, a cost of $1$ per edge, nonuniform affinities and nonuniform link lengths.
\end{theorem}
\begin{proof}
We first construct a BBC game $G$ with $n = 4$, $k = 1$, uniform
costs, nonuniform lengths, and nonuniform affinities, such that $G$
has no pure Nash equilibrium.  We then show how to extend the claim to larger
values of $n$ and $k$.

We will create $4$ nodes, as shown in Figure \ref{fig:simple_bbc_no_nash}, labeled $A$, $A^*$, $B$, and $B^*$. $A$ has and $A^*$ have positive affinity only for each other, $B$ has positive affinity only for $B^*$, and $B^*$ has positive affinity only for $A^*$. The lengths of edges $(A, B)$, $(A, B^*)$, $(B, A^*)$, and $(A^*, A)$ are all $1$, the length of edge $(B^*, A^*)$ is $2$, and the length of all other edges is $4$. 

Clearly, $A^*$ will purchase edge $(A^*, A)$ and $B^*$ will purchase edge $(B^*, A^*)$, since any other options for each of these nodes would have length $4$ and would therefore make the distance to their goal significantly further. For $A$, the strategy of choosing edge $(A, B^*)$ (giving utility $3$ for $A$) dominates the strategy of choosing edge $(A, A^*)$ (which gives utility $4$). Therefore $A$ will either choose $(A, B)$ or $(A, B^*)$. Similarly, for $B$, the strategy of choosing edge $(B, B^*)$ (which gives a utility of $4$ for $B$)dominates the strategy of choosing edge $(B, A)$ (which gives a utility $\ge 5$), so $B$ will choose either $(B, B^*)$ or $(B, A^*)$.

If $A$ purchases $(A, B^*)$, then $A$ pays $3$ regardless of what $B$ chooses. In this case $B$ will purchase $(B, A^*)$, and pay $3$ using path $B \rightarrow A^* \rightarrow A \rightarrow B^*$. However, if $B$ purchases $(B, A^*)$, then $A$ would do better to purchase $(A,B)$ and pay $2$. If $A$ does not purchase edge $(A, B^*)$, then $B$ must purchase edge $(B, B^*)$ to avoid paying the disconnection penalty, which will cause $A$ to switch back to edge $(A, B^*)$. Therefore there is no pure Nash equilibrium.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=2in]{simple_bbc_no_nash.jpg}
\caption[BBC game with no pure Nash equilibrium]{Simple example of a BBC game with no pure Nash equilibrium. $A$ has affinity only for $A^*$, $A^*$ only for $A$, $B$ only for $B^*$, and $B^*$ only for $A^*$. All edges have cost $1$ and all nodes have budget $1$. Some edge lengths are shown in the figure. The rest of the edges have length $4$. \label{fig:simple_bbc_no_nash}}
\end{center}
\end{figure}

This example can be extended to higher values of $n$ and $k$ as follows. First, add $k$ sets $S_1, S_2 \ldots, S_k$, each consisting of $k + 1$ additional nodes. Each node in a set $S_i$ has positive affinity only for the other nodes in $S_i$. Each edge to or from a node in $S_i$ has length $1$ and cost $1$. Each of $A$, $A^*$, $B$, and $B^*$ will have positive affinity for one node in each of $S_1, S_2 \ldots, S_{k-1}$, in addition to the affinities specified above.

If $n > k^2 + k + 4$, we will additional nodes as needed; call this set of additional nodes $T$. Each of these will have positive affinity for one node in each of the $k$ sets. The length of all edges from these nodes to nodes in any $S_i$ will be $1$. All other edges to or from these nodes will have length $4$.

Since a node in some $S_i$ has affinity for exactly $k$ other nodes, and has an available length $1$ edge to each of these, it will purchase exactly the set of edges to the other nodes in $S_i$. Similarly, each node in $T$ will connect exactly to the nodes for which it has positive affinity. Now, consider a node from the original game $G$. It must build at least one of its edges within the original game $G$, or else it will have to pay the disconnection penalty. Case 1: it builds only one edge within the original graph $G$. Here, the best option is to build $k-1$ edges directly to the nodes in the sets $S_i$ in which it is interested, paying $(k-1)$ plus the cost of accessing its goal node within $G$ (which is some value between $2$ and $4$ as analyzed above), or at most $k - 1 + 4 = k - 3$.  Case 2: it builds $j > 1$ than one edge within the original graph $G$. Here, only $k-j$ edges are available to access the $k-1$ goal nodes outside of $G$. In order to access more than one node with the same purchased edge, it must purchase an edge of length $4$ to one of the nodes in $T$ and use this to access at least $2$ of the goal nodes. Therefore, it will pay at least $(k-3) + (2 \times (4+1)) + $ the cost of accessing its goal node within $G$, which is at least $k-3 + 10 + 2 = k + 9 > k - 3$. So the node would do better to point only one edge into $G$, leaving the same non-equilibrium as described above.
\end{proof}

\begin{theorem}\label{thm:nonexistence2}
For any $k \ge 4$, $n \geq 2k^2 + k + 7$ there exists a BBC game with no pure Nash equilibrium ($n$ nodes, budget $k$ per node) in which only the affinities are nonuniform. All costs and lengths are $1$. 
\end{theorem}

\begin{proof}
We first construct a BBC game $G$ with $n = 28$, nonuniform $k$, uniform
costs, uniform lengths, and nonuniform affinities, such that $G$
has no pure Nash equilibrium.  We then show how to extend the claim to uniform values of $k$, and then to larger
values of $n$ and $k$.

We will create $8$ nodes, as shown in Figure \ref{fig:nonuniform_preferences_bbc_no_nash}, labeled $A$, $B$, $C$, $D$, and $E$, $p_1$, $p_2$, and $q$. As in the proof of Theorem \ref{thm:nonexistence}, we will force the edges for $C$, $E$, $D$, $p_1$, $p_2$, and $q$ by giving them positive affinities for exactly as many nodes as they can afford to link to directly. $C$ has budget $2$ and affinity only for $A$ and $D$. $E$ has budget $3$ and affinity only for $B$, $p_1$ and $q$. $D$ has budget $0$. $p_1$ has budget $1$ and affinity only for $p_2$, $p_2$ has budget $1$ and affinity only for $D$, and $q$ has budget $1$ and affinity only for $C$. Each of the nodes $C$, $D$, $E$, $p_1$, $p_2$, and $q$ will purchase exactly the edges to the nodes for which they have some affinity. 

This leaves only $A$ and $B$ with any decision to make. $A$ has budget $1$ and affinity for $B$, $C$ and $D$. $B$ has budget $1$ and affinity for $A$, $E$ and $D$. $A$ always has the option to point to $E$ and be able to access all of its preferred nodes. Therefore, $A$ will never point to $C$ or to $D$, since both of these choices will force it to pay the disconnection penalty, regardless of $B$'s choice. If $A$ points to $E$, then the best choice for $B$ is to point to $C$ (pointing to $D$ would cause it to pay the disconnection penalty, pointing to $A$ has utility $8$, pointing to $E$ has utility $9$, and pointing to $C$ has utility $7$). If $B$ points to $C$, then $A$ can improve by pointing to $B$ (paying $6$ rather than $9$ by pointing to $E$). If $A$ points to $B$, then $B$ must point to $E$ to avoid paying the disconnection penalty. If $B$ points to $E$, then $A$ will do best by also pointing to $E$ (paying $9$ rather than $10$ by pointing to $B$), causing $B$ to move back to $C$. Therefore there is no pure Nash equilibrium.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=2.4in]{nonuniform_preferences_bbc_no_nash.jpg}
\caption[BBC game with uniform lengths and costs that has no pure Nash equilibrium]{Example of a BBC game with no pure Nash equilibrium, only budget and affinity are nonuniform. All edges have cost $1$ and length $1$. $D$ has budget $0$, $C$ has budget $2$, $E$ has budget $3$, and all other nodes have budget $1$. The arrows in the figure show affinities $= 1$. The rest of the affinities are $0$. \label{fig:nonuniform_preferences_bbc_no_nash}}
\end{center}
\end{figure}

To make the budgets uniform, we can add $2(k-1) + 1$ sets of $k+1$ nodes each, call them $S_1, \ldots, S_{k-1}, T_1, \ldots, T_{k-1}, R$. Each node in each set will have affinity for each other node in the same set. $A$ will have affinity for one node in each $S_i$, $B$ will have affinity for one node in each $T_i$, and each other node will have affinity for exactly enough nodes in $R$ to fill the remainder of its budget. These new affinities force the remaining edges without changing the existing example.  See Figure \ref{fig:nonuniform_preferences_bbc_no_nash_2}.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=4.9in]{nonuniform_preferences_bbc_no_nash_2.jpg}
\caption[BBC game with uniform lengths, costs, and budgets that has no pure Nash equilibrium]{Example of a BBC game with no pure Nash equilibrium, only affinity is nonuniform. All edges have cost $1$ and length $1$. All nodes have budget $3$. The arrows in the figure show affinities $= 1$. The rest of the affinities are $0$. \label{fig:nonuniform_preferences_bbc_no_nash_2}}
\end{center}
\end{figure}

In order to extend to higher values of $n$, simply add additional nodes with affinity only for the nodes in $R$. 
\end{proof}

\begin{theorem}\label{thm:nonexistence3}
There exists a BBC game for any $n \geq 5$ with no pure Nash equilibrium in which only the costs are nonuniform and all budgets $k=2$. 
\end{theorem}

\begin{proof}
Consider the example shown in Figure \ref{fig:nonuniform_costs_bbc_no_nash}. The displayed edges have cost $1$. The rest of the edges have cost $3$. Each node has budget $2$. All lengths and affinities are uniform.  Since the edges missing from the Figure are too expensive to ever be included, $A$, $B$ or $C$ cannot remove the edges from the cycle $A \rightarrow B \rightarrow C \rightarrow A$ without paying the disconnection penalty. $D$ and $E$ cannot afford to purchase any edges. 

$A$, $B$, and $C$ can each afford one other edge, and the affordable options for each are the edge to $D$ and the edge to $E$. At least two of $A$, $B$, and $C$ must point to the same node (either $E$ or $F$). Without loss of generality, assume two of the nodes point to $E$. If both $A$ and $B$ point to $E$, then $A$'s utility is at least $7$. $A$ can switch its edge from $E$ to $F$ and get utility $6$. If both $B$ and $C$ point to $E$, then $B$'s utility is at least $7$, but $B$ can switch from $E$ to $F$ and get utility $6$. If both $A$ and $C$ point to $E$, then $C$'s utility is at least $7$, but $C$ can switch from $E$ to $F$ and get utility $6$. Therefore, for any set of legally purchased edges, some node can improve by changing an edge, so there is no equilibrium.

This can be trivially extended to larger $n$ by adding additional nodes with only cost $3$ edges into and out of these nodes. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=1in]{nonuniform_costs_bbc_no_nash.jpg}
\caption[BBC game with uniform lengths, budgets, and affinities that has no pure Nash equilibrium]{Example of a BBC game with no pure Nash equilibrium in which only the costs are nonuniform. The displayed edges cost 1. The rest of the edges cost 3. Each node has budget 2. This example can also be used to show a game with no pure Nash equilibrium in which only the lengths are nonuniform. For this case, the displayed edges have length 1, and the rest of the edges have length 4. \label{fig:nonuniform_costs_bbc_no_nash}}
\end{center}
\end{figure}
\end{proof}

\junk{
\begin{theorem}\label{thm:nonexistence4}
There exists a BBC game with no pure Nash equilibrium in which only the lengths are nonuniform. $n=5$ and $k=2$.
\end{theorem}

\begin{proof}
Consider again the example shown in Figure \ref{fig:nonuniform_costs_bbc_no_nash}. The displayed edges have length 1. The rest of the edges have length 4. Each node has budget 2. All costs and affinities are uniform. 
\end{proof}
}
\begin{theorem}
\label{thm:nphard}
It is \NP-hard to determine whether a given instance of the non-uniform
BBC game has a pure Nash equilibrium.
\end{theorem}

\begin{proof}
The proof is by a reduction from 3SAT.  Let $\phi$ be a 3SAT formula
with $n$ variables, $x_1, \ldots, x_n$, and $m$ clauses, $c_1, \ldots, c_m$.  
We create a non-uniform BBC
instance as follows.  For each variable $x_i$ in $\phi$, we introduce
3 nodes: a {\em variable node}\/ $X_i$ and two {\em truth nodes}\/
$X_{iT}$ and $X_{iF}$.  For each clause $c_j$, we introduce a clause
node $C_j$ and three intermediate nodes $I_{j1}$, $I_{j2}$, and $I_{j3}$,
one for each of the three literals in the clause.  We also have an
additional node $S$ and a gadget $G$ consisting of the nodes
illustrated in Figure~\ref{fig:simple_bbc_no_nash}.  Our construction is depicted
in Figure~\ref{fig:bbc_np_hard}.

\begin{figure}[htb]
\begin{center}
\includegraphics[height=3.17in]{bbc_np_hard.jpg}
\caption[\NP-hardness construction for finding pure Nash equilibrium in a BBC game]{Construction to prove \NP-hardness of pure
Nash Equilibrium detection \label{fig:bbc_np_hard}}
\end{center}
\end{figure}

For all $u$, $v$ in $V$, we set $\cost{u}{v}$ to be $1$.  The length
of every link shown in Figure~\ref{fig:bbc_np_hard} is $1$ and the
length of every other link is a large number $L$ greater than the
number of nodes; we set the disconnection penalty $M$ to be $nL$.  The
budget for each truth node is $0$, the budget for $S$ is $m$, and the budget for every other node is $1$.  

We now define the affinities.  Let $V$ denote the set
of all nodes. Affinities for the truth nodes are irrelevant, since they have budget $0$. 
For node $X_i$, we set $\affinity{X_i}{v}$ to be $1$ for $v \in
\{X_{iT}, X_{iF}\}$ and $0$ for all other $v$; thus, $X_i$ 
equally prefers to communicate with $X_{iT}$ and $X_{iF}$ and with no
other node. 

Now consider a clause $c_j$.  For each intermediate node $I_{jk}$, we
set $\affinity{I_{jk}}{v}$ to be $1$ if $v = X_i$ and $0$ otherwise.  If
the $k$th literal of $c_j$ is $x_i$, then for the intermediate node
$I_{jk}$, we set $\affinity{I_{jk}}{v}$ to $1$ for $v = X_{iT}$ and $0$
for all other $v$; else, we set $\affinity{I_{jk}}{v}$ to $1$ for $v =
X_{iF}$ and $0$ for all other $v$.  For the clause node $C_j$, we set
the affinities as follows.  If $x_i$ is in clause $C_j$, then
$\affinity{C_j}{X_{iT}}$ is $1$; if $\overline{x_i}$ is in clause $K_j$, then
$\affinity{C_j}{X_{iF}}$ is $1$; for all other $v$, $\affinity{C_j}{v}$ is $0$.

% why was this here? $\affinity{C_j}{S}$ is $1$ 

We next consider the gadget $G$.  The affinities of $B$, $A^*$, and $B^*$ remain the same (see the proof of Theorem \ref{thm:nonexistence}).
For node $A$, we set $\affinity{A}{A^*} = 2m - 1$, $\affinity{A}{v} = 2$ for all intermediate nodes $v$, 
and $\affinity{A}{v} = 0$ for all other nodes $v$.

For node $S$, we set $\affinity{S}{v} = 1$ if $v$ is a clause node and $0$
otherwise.  Node $S$ has a budget of $m$ and will therefore be able to reach all desired nodes each with distance $1$.

We now show that $\phi$ is satisfiable if and only if the above BBC
game has a pure Nash equilibrium.  Suppose $\phi$ is satisfiable.
Consider a satisfying assignment for $\phi$.  If $x_i$ is true, we set
the link from $X_i$ to $X_{iT}$; otherwise, we set the link from $X_i$
to $X_{iF}$; in either case, $X_i$ has attained its highest utility
possible.  The intermediate nodes just link to their respective
variable nodes and attain their best utility.  For each clause
$c_j$, there exists a literal in the clause, say the $k$th literal,
which is satisfied.  If the literal equals variable $x_i$, then the
intermediate node $I_{jk}$ has a path to $X_{iT}$ through $X_i$.  So
we set the link from the clause node $C_j$ to $I_{jk}$.  A clause node
prefers to communicate with three of the truth nodes but can
communicate with at most one in any stable network owing to budget
constraints.  Furthermore, the three-hop path achieved from the clause
node to a truth node is the shortest possible, so each clause node has
also attained its best utility.  We finally consider the nodes in
the gadget $G$.  $A^*$ and $B^*$ will still obtain their best utility by pointing to $A$ and $A^*$, respectively. 
If $A$ links to $S$, it's utility will be
\begin{align*}
& (2m - 1) \cdot (\mbox{ distance to } A^*) + \sum_{j=1}^m \sum_{d=1}^3 2 \cdot (\mbox{distance to } I_{jd}) \\
&= (2m - 1) \cdot M + \sum_{j=1}^m ((2 \cdot 3) + (2 \cdot 2 \cdot M)) \\
& = 6mM - M + 6m
\end{align*}
If $A$ were to link within $G$, its utility will be at least 
\begin{align*}
& (2m - 1) \cdot (\mbox{ distance to } A^*) + \sum_{j=1}^m \sum_{d=1}^3 2 \cdot (\mbox{distance to } I_{jd}) \\
& \geq ((2m - 1) \cdot 2) + \sum_{j=1}^m \sum_{d=1}^3 2M \\
& = 4m - 2 + 6mM \\
\end{align*}
Since $M > 2m + 2$, $A$ will link to $S$. Since $A$ is not linking to $B^*$, $B$ must link to $B^*$ to avoid paying $M$. 
Thus, the constructed network is stable.

If the BBC game has a pure Nash equilibrium, then $A$ has to link to $S$ since the gadget by itself
does not have a pure Nash equilibrium, by the proof of
Theorem~\ref{thm:nonexistence}.  Since $A$ links to $S$, it must be true that the cost to $A$ by pointing to $S$ is at most the cost to $A$ if it were to point within $G$. 
Assuming $s$ clause nodes are pointing directly to truth nodes (because they cannot access their truth nodes via intermediate nodes), the utility for $A$ pointing to $S$ is
\begin{align*}
& (2m - 1) \cdot (\mbox{ distance to } A^*) + \sum_{j=1}^m \sum_{d=1}^3 2 \cdot (\mbox{distance to } I_{jd}) \\
&=  (2m - 1) \cdot M + (s + 2m)2M + (m-s)6 \\
&=  2mM - M + 2sM + 4mM + 6m - 6s \\
&=  6mM - M + 2sM + 6m - 6s \\
\end{align*}
The utility for $A$ pointing within $G$ is at most 
\begin{align*}
& (2m - 1) \cdot (\mbox{ distance to } A^*) + \sum_{j=1}^m \sum_{d=1}^3 2 \cdot (\mbox{distance to } I_{jd}) \\
\geq & ((2m - 1) \cdot 3) + \sum_{j=1}^m \sum_{d=1}^3 2M \\
= & 6m - 3 + 6mM \\
\end{align*}
Solving for $s$ so that $6mM - M + 2sM + 6m - 6s \leq 6m - 3 + 6mM$ gives $s \leq \frac{1}{2}$, so $s$ must be $0$. This means that each clause node must be pointing to some intermediate node. A clause node links to an intermediate node only
if the intermediate node has a path either to a node $X_{iT}$, where
$x_i$ is in the clause, or to a node $X_{iF}$, where $\overline{x_i}$ is in
the clause.  This is because if no intermediate node for the clause
has such a path, then the clause node would link to $S$.  This yields
the following satisfying assignment for $\phi$: set $x_i$ to true if
$X_i$ has a link to $X_{iT}$, and false otherwise.

In the above reduction, the budget function is nonuniform.  By using
additional nodes as in the extension to higher $k$ in the proof to theorem \ref{thm:nonexistence}, the reduction can be easily adapted to work where
the budget of each node is $k$, for $k \ge m$.
\end{proof}

\newcommand{\avec}{{\bf a}}
\newcommand{\bvec}{{\bf b}}
\newcommand{\cvec}{{\bf c}}
\newcommand{\fraccost}[3]{\mbox{cost}_{#2#3}(#1)}
\newcommand{\gamename}{bounded budget connection game}

\newcommand{\nashclass}{Forest of Willows}

\section{Uniform Games}
\label{sec:bbc_uniform}
%
Although non-uniform games lack stability, the simplest version of the
framework has many interesting properties. We define a uniform
$(n,k)$-BBC game as a game in which all preferences, costs, and
lengths are 1, and each node has a budget of $k$ links. In other
words, in this graph, all the nodes are equally interested in
communicating with all other nodes, any connection can be established
for the same cost, and the utility function is calculated using hop
counts.

We show that a Nash equilibrium, or stable graph, exists for the
uniform $(n,k)$-BBC game with any values of $n$ and $k$ and that all
stable graphs are essentially fair (all nodes in a stable graphs have
similar cost). We also establish nearly tight bounds on the price of
anarchy and price of stability. We finally provide
some initial results about the dynamics of non-stable uniform graphs,
as individual nodes keep changing their links to improve their cost.
%
\subsection{Nash equilibria}
\label{sec:uniform.exist}
The main result of this section is the following.
%
\begin{theorem} \label{thm:nash}
For any $n \geq 2$ and any positive integer $k$, uniform stable $(n,k)$-graphs exist, and in any stable graph the cost of any node is $\Theta(1)$ times the cost of any other node.
The price of anarchy is $\Omega(\frac{ \sqrt{(n/k)} } { \log_k n })$, $O(\sqrt{\frac{n}{\log_k n}})$ (for $k \geq 2$). The price of stability is $\Theta(1)$.
\end{theorem}

To prove Theorem \ref{thm:nash}, we first show fairness. Then we describe a class of stable graphs for any $k$ and prove that they are stable.  The graphs in this class have total cost ranging from $O(n^2 \log_k n)$ to $\Omega(n^2 \sqrt{\frac{n}{k}})$. This gives a lower bound on the price of anarchy and the price of stability. Then, we give an upper bound on the diameter of any stable graph and use this to obtain an upper bound on the price of anarchy.

\begin{lemma}
\label{lem:fair}
Fairness: In any stable graph for the $(n,k)$-uniform game, the cost of any node
is at most $n + n \lfloor \log_k n \rfloor$ more than, and at most $2
+ 1/k + o(1)$ times, the cost of any other node.
\end{lemma}
\begin{proof}
Let $G$ be a stable graph for the $(n,k)$-uniform game and let $r$ be
a node in $G$ that has the smallest cost $C^*$.  Consider the shortest
path tree $T$ rooted at $r$.  Let $v$ be any other node.  Within
$\lfloor \log_k n \rfloor$ hops from $v$, there exists a node $u$ that
has at least one edge not in $T$.  Since $G$ is stable, node $u$ has
cost at most $C^* + n$, since it can achieve this cost by attaching
one of its links not in $T$ to $r$.  Therefore, the cost of $v$ is at
most $C^* + n + n\log_k n$, since the distance from $v$ to any node
$w$ is at most $\log_k n$ more than that of $u$ to $w$.  Noting that
$C^*$ is at least $\sum_{0 \le i < \log_k n} ik^i \ge (n - n/k)\lfloor
\log_k n \rfloor$ completes the proof of the lemma.
\end{proof}

\begin{figure}[htb] 
\begin{center}
\includegraphics[width=110mm]{avg_worst_nash.jpg} 
\caption[Class of pure Nash equilibria for uniform BBC games]{The ``\nashclass'' stable graphs: $k$ sections, each has a complete $k$-ary tree of height $h$. Under each leaf, there is a tail of length $l$. The last node in each tail has an edge to the root of each tree. The second to last node of a tail has an edge to the root of each tree other than its own. The rest of the tail nodes alternate between pointing to all the roots except their own or all the roots except one (arbitrary, but not its own). \label{fig:avg_nash}}
\end{center}
\end{figure}

In order to give an upper bound on the price of anarchy and the price of stability, we define a class of graphs that is stable. We call this class the ``\nashclass'' graphs (see Figure \ref{fig:avg_nash}). 

\begin{definition}\nashclass{} graphs:
There are $k$ directed, complete, $k$-ary trees of height $h$ (rooted at nodes $r_1, r_2, \ldots, r_k$). Each of these trees has $k^h$ leaves. Beneath each leaf, there is a tail of length $l$ ($l$ nodes not including the leaf). Let $R_i$ be the nodes in the tree rooted at $r_i$ plus the tails beneath this tree. The last node in each tail has an edge to the root of each of the $k$ trees. The second to last node of a tail in $R_i$ has an edge to each $r_j$, $j \neq i$. If a tail node in $R_i$ does not have an edge to $r_i$, the node above it has an edge to $r_i$ and any $k-2$ other roots. If a tail node in $R_i$ does have an edge to $r_i$, the node above it has an edge to each $r_j$, $j \neq i$.  We call this the \emph{initial configuration}. This graph has $n$ nodes, where $n = k * (2^{h+1} - 1 + 2^h l)$. This can be extended to other values of $n$ by adding additional leaves as evenly as possible across the trees. However, for the sake of simplicity, the following proof of stability assumes that $n$ is of the above form.
\end{definition}

We restrict $h$ and $l$ by requiring:
$$
\frac{(h+l)^2}{4} + h + 2l + 1  < \frac{n}{k}
$$

By definition of the graph structure, $h \in O(\log_k n)$. Any $l (0 \leq l < 2\sqrt{\frac{n}{k}})$ obey the requirements. Notice that $l < 2 \sqrt{\frac{n}{k}}$ implies $h > \frac{\log_2 n}{2} - \frac{\log_2 k}{2} - 1$. Also notice that the diameter of this graph is $\Theta(h+l)$, so as $k$ approaches $\frac{n}{\log^2 n}$, this class converges to a single graph: a collection of $k$ complete $k$-ary trees with edges from the leaves to the roots.

For ease of notation, we use \emph{descendants of $x$} for a node $x \in R_i$ to refer to $x$ plus all nodes $y \in R_i$ such that $x$ is on the unique shortest path from $r_i$ to $y$. We use $D_{x}$ to refer to the number of descendants of $x$. \emph{Ancestors of $x$} for $x \in R_i$ refer to all the nodes in the shortest path from $r_i$ to $x$ (not including $x$). We use $\delta_x$ to refer to the number of ancestors of $x$ (which is the same as the number of hops from $r_i$ to $x$. When $x$ is clear from the context, we use $D$ and $\delta$ instead of $D_x$ and $\delta_x$.

Since any node that is $\delta$ hops below some $r_i$ is symmetric to any other node $\delta$ hops below any $r_j$, we only need to consider whether nodes in a single $R_i$ (say $R_1$) would move any edges. None of the edges that make up the trees or the tails will be moved, or else the graph would become disconnected. So we only need to consider edges from leaf nodes or tail nodes to roots (call these \emph{non-essential edges}).

With this symmetry in mind, we must verify that no node in $R_1$ will move any of its links. First, we show for that any node $u$ in $R_j$, the number of hops from $r_j$ to $u$ times the number of descendants of $u$ is smaller than the number of nodes in $R_j$ that are \emph{not} descendants of $u$. Intuitively, this is like isolating a single potential link end point: if a node were to move one of its links from $r_j$ to $u$, the decrease to its cost would be smaller than the increase to its cost, even if the distance to each node only increased by one hop. Next, we show that a node would never move its links to one of its own ancestors or descendants, and a node would never place multiple links that have an ancestor/descendant relationship to each other. Once we've eliminated the possibility of related links, it is a relatively small step using our initial lemma to show that no node would ever place its links on non-root nodes. Finally, we show that the nodes would not move their links between roots, completing the proof that \nashclass{} graphs are stable.

The following lemma is used throughout this proof.
\begin{lemma} \label{the_math}
Let $u$ be a given node in $R_1$. If $\delta_u > 1$, then $\frac{n}{k} - D_u - l \geq D_u \delta_u$. If $\delta_u=1$, then $\frac{n}{k} - D_u \geq D_u$.
\end{lemma}

\begin{proof}
Case 1: $u$ is a tree node (so $1 \leq \delta \leq h$). Here, regardless of the values of $h$ and $l$:

\junk{if $\delta > 1$:
\begin{eqnarray*}
D &=& \frac{n}{k^{\delta + 1}} - \sum_{i=1}^{\delta} \frac{1}{k^i} < \frac{n}{k^{\delta + 1}} \\
\frac{n}{k} - D (\delta + 1) - l & > & n(\frac{1}{k} - \frac{(\delta+1)}{k^{\delta+1}}) - l \\
& \geq & n(\frac{1}{k} - \frac{2}{k^2}) - l \textrm{ since $\delta \geq 1$} \\
& \geq & \frac{n}{k^2} - l \textrm{ if $k \geq 3$} \\
& > & 0 \textrm{ since there are $k$ sections with at least $k$ tails per section.} 
\end{eqnarray*}}

if $\delta > 1$:
\begin{eqnarray*}
D &=& \frac{n}{k^{\delta + 1}} - \sum_{i=1}^{\delta} \frac{1}{k^i} < \frac{n}{k^{\delta + 1}} \\
\frac{n}{k} - D (\delta + 1) - l & > & n(\frac{1}{k} - \frac{(\delta+1)}{k^{\delta+1}}) - l  \geq \frac{n}{k^2} - l \textrm{ if $k \geq 3$, since $\delta \geq 1$} \\
& > & 0 \textrm{ since there are $k$ sections with at least $k$ tails per section.} 
\end{eqnarray*}

and
\begin{eqnarray*}
\frac{n}{k} - D (\delta + 1) - l & > & n(\frac{1}{k} - \frac{(\delta+1)}{k^{\delta+1}}) - l  \geq  \frac{n}{8} - l  > 0 \textrm{ since $h \geq 3$ }
\end{eqnarray*}

\junk{\begin{eqnarray*}
\frac{n}{k} - D (\delta + 1) - l & > & n(\frac{1}{k} - \frac{(\delta+1)}{k^{\delta+1}}) - l \\
& = & n(\frac{1}{2} - \frac{(\delta+1)}{2^{\delta+1}}) - l \textrm{ when $k=2$} \\
& \geq & \frac{n}{8} - l  \\
& >& 0 \textrm{ since $h \geq 3$ }
\end{eqnarray*}}

if $\delta = 1$:
\begin{eqnarray*}
D &=& \frac{n}{k^2} - \frac{1}{k} \\
\frac{n}{k} - 2D & = & \frac{n}{k} - \frac{2n}{k^2} + \frac{2}{k} = \frac{n(1 - \frac{2}{k}) + 2}{k} > 0 \\
\end{eqnarray*}

\junk{\begin{eqnarray*}
D &=& \frac{n}{k^2} - \frac{1}{k} \\
\frac{n}{k} - 2D & = & \frac{n}{k} - \frac{2n}{k^2} + \frac{2}{k} \\
& = & \frac{n(1 - \frac{2}{k}) + 2}{k} \\
& > & 0 \\
\end{eqnarray*}}

Case 2: $u$ is a tail node.
\begin{eqnarray*}
D &=& h + l - \delta + 1  \\
\frac{n}{k} - D (\delta + 1) - l  &=& \frac{n}{k} + \delta^2 - (h+l)(\delta +1) - l - 1 \\
\end{eqnarray*}

The second derivative with respect to $\delta$ is positive, so we only need to check this at the point where $\frac{d}{d\delta} = 0$ (a minima).
\begin{eqnarray*}
\delta&=&\frac{h}{2} + \frac{l}{2} \qquad D = \frac{h}{2} + \frac{l}{2} + 1 \\
\frac{n}{k} - D (\delta + 1) - l  &=& \frac{n}{k} - \frac{(h + l)^2}{4} - h  - 2l - 1 \\
& > & 0 \textrm{ by our restrictions on $h$ and $l$}
\end{eqnarray*}

\junk{\begin{eqnarray*}
\delta&=&\frac{h}{2} + \frac{l}{2} \\
D &=& \frac{h}{2} + \frac{l}{2} + 1 \\
\frac{n}{k} - D (\delta + 1) - l  &=& \frac{n}{k} - (\frac{h}{2} + \frac{l}{2} + 1)^2 - l \\
 &=& \frac{n}{k} - \frac{(h + l)^2}{4} - h  - 2l - 1 \\
& > & 0 \textrm{ by our restrictions on $h$ and $l$}
\end{eqnarray*}}

\end{proof}

\begin{lemma} \label{decendant_lemma}
If node $x \in R_1$ benefits by moving any of its non-essential edges to one of its descendants, and if $u_1$ is the closest such descendant, then $x$ will also benefit by moving this edge to another node (distinct from $u_1$) that is $\delta_{u_1}$ hops from a root.
\end{lemma}

\begin{proof}
Suppose $x$ placed at least one of its non-essential edges at node $u_1$, a descendant of $x$. Suppose the $k-2$ other non-essential edges were placed at nodes $u_2, u_3, \ldots u_{k-1}$, and if any other $u_j$ is also a descendant of $x$, then $\delta_{u_j} > \delta_{u_1}$.

The total decrease in hop count by moving the edges from our original placement is at most $\sum_{j=1}^{k-2} (D_{u_j} \delta_{u_j}) - D_{u_1} \delta_x$ (since the sum counts all of the descendants of $u_1$ as having a decrease of $\delta_{u_1}$, but they actually only decreased by $\delta_{u_1} - \delta_x$).

The total increase in hop count is at least $\frac{(k-1)n}{k} - \sum_{j=2}^{k-1} (D_{u_j}) - D_x$ (since each of these non-essential edges used to point to a root, and the distance to all the descendants of these roots that are not also descendants of $x$ or one of the $u_j$ will now increase by at least one hop.)

By moving to another node $\delta_{u_1}$ hops below a root (that is not an ancestor or descendant of $x$ or of any of the other $u_j$), the total decrease in hop count will increase by at least $D_{u_1} \delta_x$. Meanwhile, the increase in hop count can only get lower. Therefore, if $x$ would make the previous move, $x$ would also make the new move.
\end{proof}

\begin{lemma} \label{lem:uniform.ancestor}
If node $x \in R_1$ benefits by moving any of its non-essential edges to one of its ancestors, $u_1$ ($u_1 \neq r_1$), then $x$ will also benefit by moving this edge to another node $\delta_{u_1}$ hops from a root.
\end{lemma}

\begin{proof}
Suppose $x$ placed at least one of its non-essential edges at node
$u_1$, an ancestor of $x$. Suppose the $t-1$ other non-essential edges
were placed at nodes $u_2, u_3, \ldots u_t$ ($t$ may be $k-1$ or $k$,
depending on the location of $x$). By Lemma \ref{decendant_lemma}, we
can assume none of $u_2, \ldots u_t$ is a descendant of $x$.

The total decrease in hop count by moving the edges from our original
placement is at most $\sum_{j=1}^t (D_{u_j} \delta_{u_j}) - D_x
\delta_{u_1}$ (since the sum counts all of the descendants of $u_1$ as
having a decrease of $\delta_{u_1}$, but actually the descendants of
$x$ did not decrease at all).

The total increase in hop count is at least $\frac{tn}{k} - \sum_{j=1}^t (D_{u_j})$ (since each of these non-essential edges used to point to a root, and the distance to all descendants of these roots that are not also descendants of one of the $u_j$ will now increase by at least one hop.)

By moving to another node $\delta_{u_1}$ hops below a root (that is not an ancestor or descendant of $x$ or of any of the other $u_j$), the total decrease in hop count will increase by at least $D_x \delta_{u_1}$. Meanwhile, the increase in hop count can only get lower. Therefore, if $x$ would make the previous move, $x$ would also make the new move.
\end{proof}

\begin{lemma} \label{lem:uniform.parent_child}
If $x$ will benefit by moving any two of its non-essential edges to nodes, $\{u_1, u_2\} \in R_1$, such that $u_1$ is an ancestor of $u_2$, then it will also benefit by moving to a node $\delta_{u_1}$ hops below $r_1$ and a node $\delta_{u_2}$ hops below $r_1$ (neither of which is an ancestor or descendant of $x$ or of any other $u_j$). 
\end{lemma}
Notice there will always exist two such nodes because there are $k$ branches of each tree and at most $k$ non-essential edges, and $u_2$ must be at least 2 hops below a root, where there are $k^2$ branches (so we can always avoid an ancestor or descendant of $x$ as well).

\begin{proof}
Suppose $x$ placed two of its non-essential edges at nodes $\{u_1, u_2\}$ such that $u_1$ is an ancestor of $u_2$. Suppose the other non-essential edges were placed at nodes $u_3, u_4, \ldots u_t$ (none of which is an ancestor or descendant of $x$). Also assume there is no $u_j$ on the shortest path from $u_1$ to $u_2$.

The total decrease in hop count by moving the edges from our original placement is at most $\sum_{j=1}^t (D_{u_j} \delta_{u_j}) - D_{u_2} \delta_{u_1}$ (since the sum counts all of the descendants of $u_2$ as having a decrease of $\delta_{u_2}$, but actually the decrease was only $\delta_{u_2} - \delta_{u_1}$).

The total increase in hop count is at least $\frac{tn}{k} - \sum_{j=1}^t (D_{u_j}) + D_{u_2} - D_x$ (since each of these non-essential edges used to point to a root, and the distance to all nodes that are descendants of these roots but not of $x$ or one of the $u_j$ will now increase by at least one hop.)

By changing the move as suggested in this lemma, the total decrease in hop count will increase by at least $D_{u_2} \delta_{u_1}$. Meanwhile, the increase in hop count can only get lower. Therefore, if $x$ would make the previous move, $x$ would also make the new move.
\end{proof}

\begin{lemma}
\label{lem:tree_tail}
\nashclass{} graphs are stable.
\end{lemma}

\begin{proof}

Consider any possible selections of non-essential edges for a node $x \in R_1$. Suppose $t$ of these, $\{u_1, u_2, \ldots, u_t\}$, are moved away from the roots they point to in the initial configuration (to nodes at least one hop below a root). Also assume that no $u_i$ is an ancestor or descendant of $x$ or of any other $u_j$ (we can make this assumption because of Lemma \ref{decendant_lemma}, Lemma \ref{lem:uniform.ancestor}, and Lemma \ref{lem:uniform.parent_child}). Then, some nodes in each of $t$ trees will get at least one hop further away from $x$. $D_{u_i}$ nodes will get $\delta_{u_i}$ hops closer (for all $u_i$). $D_x (\leq l)$ nodes will stay the same distance. The change in total hop count is at least the total increase minus the total decrease.
\begin{eqnarray*}
\textrm{change in total hop count} & \geq & \frac{nt}{k} - \sum_{i=1}^t D_{u_i} - l - \sum_{i=1}^t D_{u_i} \delta_{u_i} \\
 & = & \frac{nt}{k} - \sum_{i=1}^t D_{u_i}(\delta_{u_i} + 1) - l \\
 & = & \sum_{i=1}^t \left( \frac{n}{k} - D_{u_i}(\delta_{u_i} + 1) \right) - l \\
& \geq & 0 \textrm{ if $\exists i$ such that $\delta_{u_i} > 1$, by Lemma \ref{the_math} }
\end{eqnarray*}
When $\delta_{u_i} = 1$ for all $i$, we must consider two cases.

Case 1: $x \in R_1$ does not have an edge to $r_1$ in the initial configuration (or does not move this edge). In this case, the total increase is at least $\frac{nt}{k} - \sum_{i=1}^t D_{u_i}$. (The $ - l$ is not there, because $x$ is not located under a root that increases.) This gives a change in total hop count $ \geq \frac{nt}{k} - \sum_{i=1}^t D_{u_i}(\delta_{u_i} + 1) > 0$ (by the $\delta=1$ condition in Lemma \ref{the_math}).

Case 2: $x \in R_1$ has an edge to $r_1$ in the initial configuration and moves this edge. All of the nodes $u_i$ are 1 hop below roots, and none is an ancestor of $x$. There is a single node, $u_1$, that is 1 hop from $r_1$ that is an ancestor of $x$: the distance to each of the descendants of $u_1$ that are not also descendants of $x$ (at least $D_{u_1} +1 - l$ nodes) will increase by at least 2 hops ($x$ cannot be the second to last node in a tail because it had an edge to $r_1$. If $x$ is the last node of a tail, then the new distance to $r_1$ is at least $h-1$. If $x$ is at least 2 hops from the end of a tail, then there are at least 2 hops to the closest node pointing to $r_1$).

Therefore, the total increase in trees other than $R_1$ is at least $\frac{n(t-1)}{k} - \sum_{i=1}^{t-1} D_{u_i}$, and the increase in $R_1$ is at least $2(D_{u_1} + 1 - l)$. This gives the following total change in hop count.
\begin{eqnarray*}
\textrm{change in total hop count} & \geq & \frac{n(t-1)}{k} + (2 - \delta_{u_1})D_{u_1} + 2 - 2l \\
 && - \sum_{i=1}^{t-1} D_{u_i} (\delta_{u_i} + 1)  \\
 & = & D_{u_1} + 2 - 2l + \sum_{i=1}^{t-1} \left( \frac{n}{k} - 2D_{u_i} \right) \\
& \geq & 0  \textrm{, by Lemma \ref{the_math} and the fact that } D_{u_1} \\
&& \textrm{includes at least 3 tails (when $\delta_{u_1} = 1$)} \\
&& \textrm{as long as $k > 1$ and $h \geq 3$}.
\end{eqnarray*}

Therefore, $x$ does not have incentive to move any of its non-essential edges to nodes other than roots.

Finally, we must verify that $x$ has no incentive to move an edge from one root to another.

Case 1: $x \in R_1$ has edges to all roots except $r_1$ in the initial configuration.

In this case, consider what would happen if $x$ moved an edge from some root $r_j$ to $r_1$. The distance to descendants of $r_1$ but not of $x$ would decrease by at most 1 hop, since the node beneath $x$ in the tail already has an edge to $r_1$. This is a decrease of at most $\frac{n}{k} - 2$ ($x$ has only $k-1$ non-essential edges, so at least $x$ and one node below it keep the same distance). Meanwhile, the distance to all the descendants of $r_j$ will increase by at least one hop. This gives an increase of at least $\frac{n}{k}$. Since the increase is always larger than the decrease, there is no incentive for this move.

Case 2: $x \in R_1$ has edges to all roots except some $r_j$ ($j \neq 1$) in the initial configuration.

In this case, first consider what would happen if $x$ moved an edge from $r_1$ to $r_j$. The distance to descendants of $r_1$ but not of $x$ (at least $\frac{n}{k} - l$ nodes) would increase by at least 2, since it is 2 hops to another node with an edge to $r_1$. So there is an increase of at least $\frac{2n}{k} - 2l$. The distance to the $\frac{n}{k}$ descendants of $r_j$ would decrease by 1 hop, since the node beneath $x$ already points to $r_j$. So the decrease is at most $\frac{n}{k}$. The increase is always larger than the decrease, so there is no incentive for this move.

Next consider what would happen if $x$ moved an edge from some $r_g \neq r_1$ to $r_j$. The distance to the $\frac{n}{k}$ descendants of $r_g$ would increase by 1 hop, while the distance to the $\frac{n}{k}$ descendants of $r_j$ would decrease by 1 hop. Therefore, this move does not make any difference to $x$, so $x$ has no incentive to move.
\end{proof}

\begin{lemma}\label{lem:uniform.diameter}
The diameter of any uniform stable $(n,k)$-graph ($k \geq 2$) is
$O(\sqrt{n \log_k n})$, and there is at least one node whose
distance to any other node is $O(\sqrt{n})$.
\end{lemma}

\begin{proof}
Let $G$ be a stable graph for the $(n,k)$-uniform game, and let
$\Delta$ denote the diameter of $G$, given by a path from a node
$r$ to a node $v$. Consider a shortest path tree from $r$; so the
depth of this tree is $\Delta$ and $v$ is a leaf of $T$.  Let $P$
denote the set of nodes on the path from $r$ to $v$ in $T$, not
counting $r$; so $|P| = \Delta$.  Let $C$ be the sum of distances
from $r$ to the $n-\Delta$ nodes not in $P$.  The sum of distances
from $r$ to the $\Delta$ nodes in $P$ is exactly
$\Delta(\Delta+1)/2$. So the cost of $r$ is $C +
\Delta(\Delta+1)/2$.

The cost of $v$ is at most $C + n - \Delta/2 + \Delta(\Delta/2 + 1)/4
+ \Delta(\Delta/2 + 1)/4$ since $v$ can use one of its at least two
edges to connect to $r$ and the other to connect to a node halfway
along the path from $r$ to $v$.  Simplifying, we obtain that the cost
of $v$ is at most $C + n + \Delta^2/4$.  By Lemma~\ref{lem:fair}, the
cost of $v$ is at least $C + \Delta(\Delta+1)/2 - n - n \log_k n$.  We
thus obtain the inequality:
\[
C + n + \Delta^2/4 \ge C + \Delta(\Delta+1)/2 - n - n \log_k n,
\]
yielding $\Delta = O(\sqrt{n\log_k n + 2n})$.

Using the fact that the cost of $v$ is at least $C$ (in place of the
reference to Lemma \ref{lem:fair}) in the above proof gives the second
part of the lemma.
\end{proof}

\begin{LabeledProof}{Theorem \ref{thm:nash}}
The first claim directly follows from Lemma~\ref{lem:fair}.  In any
graph with max degree $k$, every node must have cost at least
$\Omega(n \log_k n)$. \nashclass{} graphs with $l=0$ have total cost
per node $O(n \log_k n)$. Therefore, the price of stability is
$\Theta(1)$.  

If $l=0$, a \nashclass{} graph has total cost per node = $O(n \log_k
n)$. Therefore, the social utility has total cost (over all nodes)
$O(n^2 \log_k n)$. If $l=\Omega(\sqrt{\frac{n}{k}})$, the total cost
(over all nodes) is $\Omega(n^2 \sqrt{\frac{n}{k}})$.  Therefore, the
price of anarchy is $\Omega(\frac{ \sqrt{(n/k)} } { \log_k n })$.

Finally, Lemma \ref{lem:uniform.diameter} implies that the total cost
of any node in the worst Nash equilibrium cannot be higher than
$O(\sqrt{n
\log_k n})$, so the total cost is $O(n \sqrt{n \log_k n})$.  We
already know that the social equilibrium is at least $O(n \log_k
n)$. Therefore, the price of anarchy is $O(\sqrt{\frac{n}{\log_k
n}})$.
\end{LabeledProof}

\subsection{Dynamics of best response walks}
\label{sec:uniform.dynamics}
Given the existence of pure Nash equilibria for $(n,k)$-uniform games,
it is natural to ask whether an equilibrium can be obtained by a
sequence of local links changes.  In particular, we consider a
specific type of best response walk: in each step, a node tests for
its stability and, if it is not stable, moves its links to the set of
nodes that optimize its cost.  We assume for convenience that only one
node attempts to change its links in any step of the best response
walk.

We first show that, starting from any initial state, the best response
walk converges to a strongly connected graph in $O(n^2)$ steps, as
long as every node is allowed to execute a best response step once
every $n$ steps.  Furthermore, there exists an initial state such that
a best response walk takes $\Omega(n^2)$ steps to converge to strong
connectivity. We next study convergence to stability and show that
there exists an initial state from which a particular best response
walk does not converge to a stable graph.  This means that the
$(n,k)$-uniform game is {\em not an ordinal potential game}, a
characteristic which justifies our use of a constructive proof for the
existence of Nash equilibria.
\junk{We also present results of some experiments that
study convergence to stability starting from regular and
semi-random graphs.}

\medskip
\BfPara{Convergence to a strongly connected graph}
For a given node $u$, we define the \emph{reach} of $u$ to be the
number of nodes to which it has paths.  Since the cost of
disconnection is assumed to be $M > n$, when we execute a best-response step
for a node $u$, the reach of $u$ cannot decrease. 

\begin{lemma}
\label{lem:reach}
Suppose the graph $G$ is not strongly connected, and a node $u$
changes its edges according to a best response step.  Then, after the
step, the reach of any node other than $u$ either remains the same or
is at least the new reach of $u$.
\end{lemma}
\begin{proof}
If a node $v$ has a path to $u$, then the reach of $v$ is at least the
reach of $u$ after the best response step.  Otherwise, the reach of
$v$ does not change.  \junk{Let $r = \reach(u)$.  Let $S_<$, $S_=$, and
$S_>$ denote the set of nodes with reach smaller than, equal to, and
greater than $r$ before the best response step.  Similarly, let
$S'_<$, $S'_=$, and $S'_>$ denote the set of nodes with reach smaller
than, equal to, and greater than $r$ after the best response step.
Then, we obtain $S'_< = S_<$ and $|S'_=| < |S_=|$ since the reach of
$u$ increases after the step and the reach of any node in $S_= \cup
S_>$ is greater than $r$ after the best response step.  Therefore,
$\Reach'$ is lexicographically larger than $\Reach$.}
\end{proof}
The above lemma indicates that whenever a best response step causes a
change, the vector that consists of all the reach values in increasing
order becomes lexicographically larger.  In order to show convergence,
we need to argue progress.  We will do so by showing that whenever the
graph is not strongly connected, there exists a node that can
improve its reach.  In fact, we use a stronger property that allows
us to bound the convergence time.

Consider best response walks that operate in a round-robin manner.
In each round, each node (one at a time in an arbitrary order) executes a
best response step.  The order may vary from
round to round. Let $G_r$ refer to the graph before round $r$.
\begin{lemma}
\label{lem:progress}
If $G_r$ is not strongly connected at the start of round $r$, then
the minimum reach increases by at least one during the round.
\end{lemma}
\begin{proof}
Consider the strongly connected components of the given graph $G_r$.
Consider the component graph $CG$ in which we have a vertex for each
strongly connected component and edge between two components whenever
there is an edge from a vertex in one component to the other.  This
graph is a dag.  Let $m$ denote the minimum reach in $G_r$.  By
Lemma~\ref{lem:reach}, nodes with reach greater than $m$ will continue
to have reach greater than $m$.  So we only need to consider nodes
with reach $m$.  All of these nodes lie in sink components.

Consider any sink component $C$.  We first argue that there exists a
node in $C$ that can improve its reach by executing a best response
step.  Consider a vertex $u$ in $C$ that has an edge from a vertex $v$
in another component.  Let $w$ be a vertex in the sink component that
has an edge to $u$.  All of $u$, $v$, and $w$ exist by definition of
strongly connected components (and our assumption that the out-degree
of every vertex is at least 1).  If $w$ replaces the edge $(w,u)$ with
$(w,v)$, it can reach all vertices in the sink
component as well as the component containing $v$.  The latter set is
clear; for the former set, note that all we have done is "replace" the
direct edge $(w,u)$ by the two-hop path $w \rightarrow u \rightarrow
v$.

For any sink component $C$, let $v$ be the first node in $C$ in the
round order that improves its reach through a best response step.
Note that $v$ exists by the argument of the preceding paragraph.
Furthermore, in the step prior to $v$'s best response, the reach of
every node in $C$ is $m$.  After $v$'s best response, the reach of $v$
increases to at least $m + 1$, as does that of \emph{every} node in $C$,
since they each have a path to $v$.  By Lemma~\ref{lem:reach}, after
every subsequent step, the reach of any node in $C$ is at least $m +
1$.  Therefore, it follows that at the end of the round, the reach of
every node in a sink component of $CG$ increases; hence, the minimum
reach increases, completing the proof of the lemma.
\end{proof}

\begin{theorem}
\label{thm:converge}
The best response walk converges to a strongly connected graph in
$n^2$ steps.
\end{theorem}
\begin{proof}
By Lemma~\ref{lem:progress}, the minimum reach increases by at least
one.  Since the initial reach is $1$ and the maximum reach is $n$, the
number of steps for the best response walk to converge to a strongly
connected graph is at most $n^2$.
\end{proof}

The above theorem is essentially tight. In the following scenario (with $k=1$), a best response walk may take $\Omega(n^2)$ steps
to converge to a strongly connected graph. Consider a graph $G$ of $n
= r + p$ nodes that is a directed ring over $r \ge n/2$ nodes together
with a directed path of $p = n - r$ nodes that ends at one of the
nodes in the ring.  Suppose a round begins at the tail $T$ of the
directed path, which can reach all nodes, proceeds along the path and
then along the ring in the direction of the ring.  The $p$ nodes on
the path cannot improve their reach.  Furthermore, the first $r - p$
nodes on the ring (in round-robin order) also cannot improve their
reach in a best response step.  The $(r - p + 1)$st node can improve
its reach by connecting to $T$, yielding a new graph $G'$ that is a
directed ring over $r + 1$ nodes and a directed path of $n - r$ nodes.
If we repeat this process, the number of steps to converge is
$\Omega(n^2)$.

\medskip
\BfPara{Cycles in best response walks}
Unlike strong connectivity, convergence to a pure Nash equilibrium is
not guaranteed.  In the following simple example, a round-robin
best-response walk contains loops. This simple example is a
(7,2)-uniform game that starts from the top-left configuration of
Figure~\ref{fig:looping}. The nodes take turns in round-robin order,
starting with node 6 then nodes 0,1,2, and so on. Tracing the example,
one can verify that after 6 deviations (nodes $6,3,2,6,3,2$ re-linking
in this order, implying that missing nodes are stable), the graph
returns to the initial configuration thus completing a loop.

\begin{figure}[tbh]
\centerline{
\subfloat[node 6 rewires to 0,2]{\includegraphics[width=1.87in]{loop1.jpg}}
\hfil
\subfloat[node 3 rewires to 5,6]{\includegraphics[width=1.87in]{loop2.jpg}}}
\centerline{
\subfloat[node 2 rewires to 0,3]{\includegraphics[width=1.87in]{loop3.jpg}}
\hfil
\subfloat[node 6 rewires to 2,5]{\includegraphics[width=1.87in]{loop4.jpg}}}
\centerline{
\subfloat[node 3 rewires to 0,6]{\includegraphics[width=1.87in]{loop5.jpg}}
\hfil
\subfloat[node 2 rewires to 3,5]{\includegraphics[width=1.87in]{loop6.jpg}}}
\caption[Loop in a best-response walk for a uniform BBC game]{An example in which a round-robin best-response walk loops. Starting from the top left configuration and following a
round-robin best-response walk $6\rightarrow 0 \rightarrow 1 \rightarrow \ldots \rightarrow 6 \rightarrow 1 \ldots$ we get back to
the initial configuration after 6 deviations (nodes $6,3,2,6,3,2$). Turns that are not illustrated imply stable
nodes. Next to each node we indicate its cost under the current configuration.}
\label{fig:looping}
\end{figure}

The above example of a loop in the best response walk shows that the uniform-$(n,k)$-game
is not an ordinate potential game. However, the loop does not rule
out the possibility that either (a) a well-chosen best response walk
converges from any initial state, or (b) certain best response walks
do converge to stability if started from simple initial configurations such
as the empty graph.  

\junk{
We have observed experimentally that best response walks in which a node with the
maximum cost always makes the next best response step does not always converge
to a stable graph. However, based on our experimental data, this best response walk 
starting from an empty graph does seem to converge to a stable graph. Our experiments
also suggest that there may be some exponentially long best-response paths that start
in some non-empty initial configuration and end at a stable graph.
}

\section{Max distance utility function}
\label{sec:bbc_max}
In the BBC games we have studied thus far, the utility of a node $u$
in $G(S)$ given by $- \sum_{v} \affinity{u}{v} d(u,v)$, where $d(u,v)$ is
the shortest path from $u$ to $v$ in $G(S)$ according to the lengths
given by $\lengthonearg{u}$.  In this section, we also consider a natural variant
of the utility function: the utility of $u$ is $- \max_{v}
\affinity{u}{v} d(u,v)$. In order to make it clear that we are using a
different cost function, we will call the max distance version
\emph{max-BBC games}. In max-BBC games, the new utility function is $- \max_{v} \affinity{u}{v} d(u,v)$.

As with the previous cost function, we show there exist instances of
the general max-BBC game that have no Nash equilibrium.  On the other hand, if we
restrict ourselves to the uniform version (uniform $(n,k)$-max-BBC
game), there is a stable graph for any $n$ and $k < n$.  It turns out
that ratio between the total utility achieved in a Nash equilibrium in
a uniform max-BBC game and the social optimum could be much worse than
in BBC games.  In particular, we establish a lower bound of
$\Omega(\frac{n}{k \log_k n})$ on the price of anarchy in max-BBC
games. Since any two nodes can be at most distance $n$ apart, and since the diameter of a degree $k$ graph must be at least $\log_k n$, the price of anarchy has a trivial upper bound of $O(\frac{n}{\log_k n})$.

\begin{theorem}\label{thm:max.nonexistence}
For any $k \geq 4, n \geq 2k^2 + k + 7$, there exists a nonuniform max-BBC game with no pure Nash
equilibrium ($n$ nodes, budget $k$ per node) in which only the affinities are nonuniform. All
costs and lengths are 1. 
\end{theorem}

\begin{proof}
Consider the same example as shown above in Figure \ref{fig:nonuniform_preferences_bbc_no_nash_2} for the proof of Theorem \ref{thm:nonexistence2}. All costs and lengths are $1$, all budgets are $3$. The arrows show the non-zero affinities. Those nodes with positive affinity for only $3$ other nodes will point to those nodes and have a max distance of $1$. This leaves only nodes $A$ and $B$ with variable edges. $A$ must point to $S_1$ and $S_2$ or else pay the disconnection penalty, and $B$ must point to $T_1$ and $T_2$. This leaves one edge each to spare. 

$A$ always has the option to point to $B^*$ and be able to access all of its preferred nodes. Therefore, $A$ will never point to $A^*$ or to $D$, since both of these choices will force it to pay the disconnection penalty, regardless of $B$'s choice. If $A$ points to $B^*$, then the options for $B$ are: (a) point to $A$, and have max distance $5$ to $D$, (b) point to $A^*$ and have max distance $3$ to $B^*$, (c) point to $B^*$ and have max distance $4$ to $A$, or (d) point to $q$ (the node between $B^*$ and $A^*$) and have max distance $4$ to $B^*$. All other choices will force it to pay the disconnection penalty. Therefore, $B$ will point to $A^*$. In this case, $A$ has max distance $4$ to $D$, but $A$ can improve by pointing to $B$, getting max distance $2$. However, if $A$ points to $B$, then $B$ can only access all of its nodes by pointing to $B^*$, so $B$ will move its edge. Now, $A$ can improve by moving back to $B^*$. Therefore there is no pure Nash equilibrium.

As in the proof to Theorem \ref{thm:nonexistence2}, we can extend this to higher values of $n$ by adding additional nodes with affinity only for $k$ of the nodes in $R$. 
\end{proof}

\junk{
\begin{theorem}
\label{thm:nphard}
It is \NP-hard to determine whether a given instance of the non-uniform max-BBC game has a pure Nash equilibrium.
\end{theorem}

\begin{proof}
PROBLEM: A CANNOT ACCESS ALL OF ITS PREFERRED NODES. CASE 1: IT CAN ACCESS M OF THE INTERMEDIATE NODES AND POINTS TO S. THEN MAX DISTANCE = MAX(M x PREF FOR A*, M x PREF FOR INT. NODES). CASE 2: CAN ACCESS M OF THE INTERMEDIATE NODES AND POINTS IN GADGET. MAX DISTANCE = M x PREF FOR INT. NODES. CASE 3: IT CANNOT ACCESS M OF THE INTERMEDIATE NODES AND POINTS TO S. MAX DISTANCE = MAX(M x PREF FOR A*, M x PREF FOR INT. NODES. CASE 4: IT CANNOT ACCESS M OF THE INT NODES AND POINTS WITHIN THE GADGET. MAX DISTANCE = M x PREF FOR INT. NODES. SO IT DOESN'T MATTER WHETHER OR NOT IT CAN ACCESS M OF THE INTERMEDIATE NODES.

We can use the same reduction as for the original BBC game, depicted in \ref{fig:bbc_np_hard}. 

First, it is easy to verify that the gadget in Figure \ref{} still does not have an equilibrium. This is true since each node has positive affinity for only one node, so the max utility function is identical to the average utility function.

It is also easy to verify that if the 3-SAT instance can be satisfied, then we can find an equilibrium (the same one as above). In this case many of the nodes can change their edges and not do worse, since they have a max distance that is quite long, but a Nash equilibrium only requires that there is no way for them to improve.

We will verify  that there are no other equilibria.

If the BBC game has a pure Nash equilibrium, then $A$ has to link to $S$ since the gadget by itself
does not have a pure Nash equilibrium, since the gadget does not have an internal equilibrium.  Since $A$ links to $S$, it must be true that the cost to $A$ by pointing to $S$ is at most the cost to $A$ if it were to point within $G$. 
Assuming $s$ clause nodes are pointing directly to truth nodes (because they cannot access their truth nodes via intermediate nodes), the utility for $A$ pointing to $S$ is
\begin{eqnarray*}
&& (2m - 1) * \mbox{ distance to } A^* + \sum_{j=1}^m \sum_{d=1}^3 2 * \mbox{distance to } I_{jd} \\
&= & (2m - 1) * M + (s + 2m)2M + (m-s)6 \\
&= & 2mM - M + 2sM + 4mM + 6m - 6s \\
&= & 6mM - M + 2sM + 6m - 6s \\
\end{eqnarray*}
$A$'s utility pointing within $G$ is at most 
\begin{eqnarray*}
&& (2m - 1) * \mbox{ distance to } A^* + \sum_{j=1}^m \sum_{d=1}^3 2 * \mbox{distance to } I_{jd} \\
& \geq & ((2m - 1) * 3) + \sum_{j=1}^m \sum_{d=1}^3 2 * M \\
& = & 6m - 3 + 6mM \\
\end{eqnarray*}
Solving for $s$ so that $6mM - M + 2sM + 6m - 6s \leq 6m - 3 + 6mM$ gives $s \leq \frac{1}{2}$, so $s$ must be $0$. This means that each clause node must be pointing to some intermediate node. A clause node links to an intermediate node only
if the intermediate node has a path either to a node $X_{iT}$, where
$x_i$ is in the clause, or to a node $X_{iF}$, where $\overline{x_i}$ is in
the clause.  This is because if no intermediate node for the clause
has such a path, then the clause node would link to $S$.  This yields
the following satisfying assignment for $\phi$: set $x_i$ to true if
$X_i$ has a link to $X_{iT}$, and false otherwise.

\end{proof}
}

%
\begin{theorem}
\label{thm:pofa_max}
The Price of Anarchy for uniform $(n,k)$ max-BBC games is $\Omega(\frac{n}{k \log_k n})$.
\end{theorem}

\begin{proof}
Consider the following graph for $k>2$. There are $2k - 1$ tails,
$\{t_1, t_2, \ldots, t_{2k-1}\}$, each of length $l =
\frac{n-1}{2k-1}$. There is also one ``root'' node $r$ with edges to
the top node in $t_1, t_2, \ldots, t_k$. For ease of notation, we will
define segments $S_1 = \{r, t_1, t_2, \ldots, t_k\}$, $S_2 =
\{t_{k+1}\}, S_2 = \{t_{k+2}\}, \ldots, S_k = \{t_{2k-1}\}$, with the
head of each segment $S_i$ ($i>1$) = the first node of the tail, and
the head of $S_1 = r$. The last node of each tail points to the head
of each segment. The rest of the nodes in each tail point to $r$ and
to the last node of a tail. The location of the rest of the edges
don't matter, because there will not be enough remaining edges to decrease the distance to all of the nodes that are currently furthest away. 
See Figure ~\ref{fig:max_bad_nash}.  We will show that
this graph is a Nash equilibrium.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=140mm]{max_worst_nash.jpg} 
\caption[High cost pure Nash equilibrium for max-BBC game]{A high cost Nash equilibrium for the max distance cost function: $2k-1$ paths, one node points to $k$ of them. 
Each node at the end of a path points to the start of the first $k-1$ paths and the extra node. Each node in a path points to the 
node at the end of the path and to the extra node. The rest of the edges don't matter. \label{fig:max_bad_nash}
}
\end{center}
\end{figure}

First consider whether a node at the end of a tail would benefit by
moving any of its edges. Its current max distance is $2 + l$ (to a node
at the end of $t_1$, $t_2$, or $t_3$). If it does not have one edge to
each segment, then the max distance is at least $2 + l$ (since it
takes at least one hop to get to a node that will point to the
segment, and all other nodes that point to the segment point to the
head). If the one edge pointing to some segment does not point to the
head of the segment, the max distance is 1 (to get to the segment) +
the distance to the end of the tail + 1 (to get to the head) + the
distance back to where it started, adding up to $2 + l$.

Next, consider whether a node in the middle of a tail would benefit by
moving any of its edges. Its current max distance is $2 + l$ (the same
distance to the end of any tail other than the tail it lives in). In
order to get closer to the end of \emph{every} other tail (since all
are currently the same max distance), it would need to point closer to
the middle of each tail. For segments $S_2, \ldots S_k$ (other than
its own segment), this would be possible by pointing an edge to the
head of each segment (or anywhere within the segment). In order to
shorten all of these distances, at least $k-2$ edges must be
used. However, the only way to reduce the distance to nodes in $S_1$
would be to point an edge to each of the $k$ tails within the segment
(or to $k-1$ edges if this node lives in $S_1$). There are not enough
edges to improve distances to $S_1$ and to all other tails. Therefore,
this node cannot improve its utility.

This example can be extended to the case where $k=2$ with a small adjustment. In this case, there are 3 paths plus one node that points to the head of two of the paths. The nodes at the end of each path point to the root of the single path and the extra node. The second to last nodes in the other paths point to the extra node. The rest of the nodes in the other paths point to the end of a tail.

In the Forest of Willows graphs described in Section
\ref{sec:uniform.exist}, when $l$ is $0$, the sum of the max distances is
$O(n \log_k n)$. Therefore, the social optimum cost is at most $O(n
\log_k n)$. We have just shown that there is a stable network in which the sum of
the max distances is $\Omega(\frac{n^2}{k})$. Therefore, the Price of
Anarchy is $\Omega(\frac{n}{k \log_k n})$.
\end{proof}

\begin{theorem}
\label{thm:pofs_max}
The Price of Stability for uniform $(n,k)$ max-BBC games is $\Theta(1)$.
\end{theorem}

\begin{proof}
It is easy to verify that the Forest of Willows graphs with $l=0$
(described in section \ref{sec:uniform.exist}) are also stable under
the max cost function. Obviously, no node can have max distance less
than $\log_k n$. Therefore, the social optimum is at most $O(n \log_k
n)$, and the best Nash is at least $\Omega(n \log_k n)$, so Price of
Stability is $\Theta(1)$.
\end{proof}

\section{Concluding Remarks}

The results from this chapter are somewhat disheartening for the notion of decentralized overlay networks. We have shown that even when the problem definition is quite simple, there may be no stable networks. For instance, even if all of the edge lengths and costs are the same and only the affinities are different for different nodes, there may be no stable set of edges. This is true whether the utility function is based on the average distance or on the maximum distance. If the costs, budgets, lengths, and affinites are all uniform, then we can guarantee that a stable network exists. However, best response walks (a natural progression of edge selection) may cycle, even in the uniform case. Furthermore, there exist equilibria in which the average utility for a node is quite a bit worse than in a network created by a centralized algorithm. This implies that if nodes were left to choose their own edges, even if they reached a stable network, the network may have a high diameter, and the nodes may be collectively unhappy with the overall results.

In another example of a network creation game -- the Stable Paths Problem -- it has been shown that allowing fractional solutions will guarantee that an equilibrium always exists \cite{HaxellWilfong08}. In the next chapter, we use this same technique for BBC games. By allowing fractional edges, we define a bounded budget network creation game in which a stable solution always exists. We study the computational complexity of both the fractional version of BBC and the fractional version of the Stable Paths Problem.

\junk{
\section{Open Problems}
\begin{itemize}
\item \BfPara{Nonuniform Budget} We have shown that it is \NP-hard to find a pure Nash equilibrium in a BBC game in which any one of link costs, link lengths or affinity weights is nonuniform. However, we have not settled the hardness if only the budgets are non-uniform (link costs, link lengths, and affinities are all 1).
\item \BfPara{Universal Destination} In section \ref{sec:fractionalGames}, we discuss a fractional variant of BBC games, but we restrict ourselves to instances with a universal destination node. In other words, all nodes have affinity weight 1 for the same single node, and have affinity weight 0 for all other nodes. What is the hardness of fin
}